Adaptive Transfer Learning.
Discriminative learning methods are widely used in natural language processing. These methods work best when their training and test data are drawn from the same distribution. For many NLP tasks, however, we are confronted with new domains in which labeled data is scarce or non-existent. In such cases, we seek to adapt existing models from a resourcerich source domain to a resource-poor target domain. We introduce structural correspondence learning to automatically induce correspondences among features from different domains. We test our technique on part of speech tagging and show performance gains for varying amounts of source and target training data, as well as improvements in target domain parsing accuracy using our improved tagger. 1
Gaussian Process Latent Random Field.

Transductive Learning on Adaptive Graphs.

Multi%2Dtask warped Gaussian process for personalized age estimation.
Automatic age estimation from facial images has aroused research interests in recent years due to its promising potential for some computer vision applications. Among the methods proposed to date, personalized age estimation methods generally outperform global age estimation methods by learning a separate age estimator for each person in the training data set. However, since typical age databases only contain very limited training data for each person, training a separate age estimator using only training data for that person runs a high risk of overfitting the data and hence the prediction performance is limited. In this paper, we propose a novel approach to age estimation by formulating the problem as a multi-task learning problem. Based on a variant of the Gaussian process (GP) called warped Gaussian process (WGP), we propose a multi-task extension called multi-task warped Gaussian process (MTWGP). Age estimation is formulated as a multi-task regression problem in which each learning task refers to estimation of the age function for each person. While MTWGP models common features shared by different tasks (persons), it also allows task-specific (person-specific) features to be learned automatically. Moreover, unlike previous age estimation methods which need to specify the form of the regression functions or determine many parameters in the functions using inefficient methods such as cross validation, the form of the regression functions in MTWGP is implicitly defined by the kernel function and all its model parameters can be learned from data automatically. We have conducted experiments on two publicly available age databases, FG-NET and MORPH. The experimental results are very promising in showing that MTWGP compares favorably with state-ofthe-art age estimation methods. 1.
SED supervised experimental design and its application to text classification.
In recent years, active learning methods based on experimental design achieve state-of-the-art performance in text classification applications. Although these methods can exploit the distribution of unlabeled data and support batch selection, they cannot make use of labeled data which often carry useful information for active learning. In this paper, we propose a novel active learning method for text classification, called supervised experimental design (SED), which seamlessly incorporates label information into experimental design. Experimental results show that SED outperforms its counterparts which either discard the label information even when it is available or fail to exploit the distribution of unlabeled data.
Transfer metric learning by learning task relationships.
Distance metric learning plays a very crucial role in many data mining algorithms because the performance of an algorithm relies heavily on choosing a good metric. However, the labeled data available in many applications is scarce and hence the metrics learned are often unsatisfactory. In this paper, we consider a transfer learning setting in which some related source tasks with labeled data are available to help the learning of the target task. We first propose a convex formulation for multi-task metric learning by modeling the task relationships in the form of a task covariance matrix. Then we regard transfer learning as a special case of multitask learning and adapt the formulation of multi-task metric learning to the transfer learning setting for our method, called transfer metric learning (TML). In TML, we learn the metric and the task covariances between the source tasks and the target task under a unified convex formulation. To solve the convex optimization problem, we use an alternating method in which each subproblem has an efficient solution. Experimental results on some commonly used transfer learning applications demonstrate the effectiveness of our method.
SED supervised experimental design and its application to text classification.
In recent years, active learning methods based on experimental design achieve state-of-the-art performance in text classification applications. Although these methods can exploit the distribution of unlabeled data and support batch selection, they cannot make use of labeled data which often carry useful information for active learning. In this paper, we propose a novel active learning method for text classification, called supervised experimental design (SED), which seamlessly incorporates label information into experimental design. Experimental results show that SED outperforms its counterparts which either discard the label information even when it is available or fail to exploit the distribution of unlabeled data.
MILD Multiple%2DInstance Learning via Disambiguation.
In multiple-instance learning (MIL), an individual example is called an instance and a bag contains a single or multiple instances. The class labels available in the training set are associated with bags rather than instances. A bag is labeled positive if at least one of its instances is positive; otherwise, the bag is labeled negative. Since a positive bag may contain some negative instances in addition to one or more positive instances, the true labels for the instances in a positive bag may or may not be the same as the corresponding bag label and, consequently, the instance labels are inherently ambiguous. In this paper, we propose a very efficient and robust MIL method, called MILD (Multiple-Instance Learning via Disambiguation), for general MIL problems. First, we propose a novel disambiguation method to identify the true positive instances in the positive bags. Second, we propose two feature representation schemes, one for instance-level classification and the other for bag-level classification, to convert the MIL problem into a standard single-instance learning (SIL) problem that can be solved by well-known SIL algorithms, such as support vector machine. Third, an inductive semi-supervised learning method is proposed for MIL. We evaluate our methods extensively on several challenging MIL applications to demonstrate their promising efficiency, robustness and accuracy.
A regularization framework for multiclass classification A deterministic annealing approach.

Localized content%2Dbased image retrieval through evidence region identification.

Heteroscedastic Probabilistic Linear Discriminant Analysis with Semi%2Dsupervised Extension.

Semi%2DSupervised Multi%2DTask Regression.





Human action recognition using Local Spatio%2DTemporal Discriminant Embedding.

Semi%2DSupervised Discriminant Analysis using robust path%2Dbased similarity.

Learning Two%2DView Stereo Matching.

Structuring Visual Words in 3D for Arbitrary%2DView Object Localization.

Semi%2Dsupervised Discriminant Analysis Via CCCP.


Posterior Consistency of the Silverman g%2Dprior in Bayesian Model Choice.
Kernel supervised learning methods can be unified by utilizing the tools from regularization theory. The duality between regularization and prior leads to interpreting regularization methods in terms of maximum a posteriori estimation and has motivated Bayesian interpretations of kernel methods. In this paper we pursue a Bayesian interpretation of sparsity in the kernel setting by making use of a mixture of a point-mass distribution and prior that we refer to as “Silverman’s g-prior.” We provide a theoretical analysis of the posterior consistency of a Bayesian model choice procedure based on this prior. We also establish the asymptotic relationship between this procedure and the Bayesian information criterion. 1

A Scalable Kernel%2DBased Semisupervised Metric Learning Algorithm with Out%2Dof%2DSample Generalization Ability.

Robust path%2Dbased spectral clustering.
Spectral clustering and path-based clustering are two recently developed clustering approaches that have delivered impressive results in a number of challenging clustering tasks. However, they are not robust enough against noise and outliers in the data. In this paper, based on M-estimation from robust statistics, we develop a robust path-based spectral clustering method by defining a robust path-based similarity measure for spectral clustering. Our method is significantly more robust than spectral clustering and path-based clustering. We have performed experiments based on both synthetic and real-world data, comparing our method with some other methods. In particular, color images from the Berkeley Segmentation Dataset and Benchmark are used in the image segmentation experiments. Experimental results show that our method consistently outperforms other methods due to its higher robustness.
Image Hallucination Using Neighbor Embedding over Visual Primitive Manifolds.

Locally Smooth Metric Learning with Application to Image Retrieval.
In this paper, we propose a novel metric learning method based on regularized moving least squares. Unlike most previous metric learning methods which learn a global Mahalanobis distance, we define locally smooth metrics using local affine transformations which are more flexible. The data set after metric learning can preserve the original topological structures. Moreover, our method is fairly efficient and may be used as a preprocessing step for various subsequent learning tasks, including classification, clustering, and nonlinear dimensionality reduction. In particular, we demonstrate that our method can boost the performance of content-based image retrieval (CBIR) tasks. Experimental results provide empirical evidence for the effectiveness of our approach. 1.
Kernel selection forl semi%2Dsupervised kernel machines.

A kernel path algorithm for support vector machines.
The choice of the kernel function which determines the mapping between the input space and the feature space is of crucial importance to kernel methods. The past few years have seen many efforts in learning either the kernel function or the kernel matrix. In this paper, we address this model selection issue by learning the hyperparameter of the kernel function for a support vector machine (SVM). We trace the solution path with respect to the kernel hyperparameter without having to train the model multiple times. Given a kernel hyperparameter value and the optimal solution obtained for that value, we find that the solutions of the neighborhood hyperparameters can be calculated exactly. However, the solution path does not exhibit piecewise linearity and extends nonlinearly. As a result, the breakpoints cannot be computed in advance. We propose a method to approximate the breakpoints. Our method is both efficient and general in the sense that it can be applied to many kernel functions in common use. 1.
A Scalable Kernel%2DBased Algorithm for Semi%2DSupervised Metric Learning.

Boosting Kernel Discriminant Analysis and Its Application on Tissue Classification of Gene Expression Data.
Abstract — This paper addresses the problem of object classification in a biosonar based mobile robot in a natural environment using a boosting method. We present an algorithm based on gradient boosting for biosanar-based robots that recognize different objects such as different trees via reflected sonar echoes. Gradient boosting is a machine learning approach, that builds one strong classifier from many base learners. We present two kinds of base learners for the gradient boosting: Ordinary Least Squares (OLS) and kernel-based base learners. Compared with our previous works, in which we presented a time resolved spectrum kernel to extract the similarities between echoes, we get more efficient and accurate results with the newly proposed boosting method. We compare the methods in terms of sensitivity, specificity, accuracy and Matthew’s correlation coefficient and also the runtime of training and testing. I.
Semi%2Dsupervised Cast Indexing for Feature%2DLength Films.

A Kernel Approach for Semisupervised Metric Learning.

Kernel%2Dbased distance metric learning for content%2Dbased image retrieval.


Surrogate maximization%2Fminimization algorithms and extensions.


Learning the kernel matrix by maximizing a KFD%2Dbased class separability criterion.
The advantage of a kernel method often depends critically on a proper choice of the kernel function. A promising approach is to learn the kernel from data auto-matically. In this paper, we propose a novel method for learning the kernel matrix based on maximizing a class separability criterion that is similar to those used by linear discriminant analysis (LDA) and kernel Fisher discriminant (KFD). It is in-teresting to note that optimizing this criterion function does not require inverting the possibly singular within-class scatter matrix which is a computational problem encountered by many LDA and KFD methods. We have conducted experiments on both synthetic data and real-world data from UCI and FERET, showing that our method consistently outperforms some previous kernel learning methods.
Structural
In this paper we explore a new theory of discourse structure that stresses the role of purpose and processing in discourse. In this theory, discourse structure is composed of three separate but interre-lated components: the structure of the sequence of utterances (called the linguistic structure), a struc-ture of purposes (called the intentional structure), and the state of focus of attention (called the attentional state). The linguistic structure consists of segments of the discourse into which the utter-ances naturally aggregate. The intentional structure captures the discourse-relevant purposes, expressed in each of the linguistic segments as well as relationships among them. The attentional state is an abstraction of the focus of attention of the participants as the discourse unfolds. The attentional state, being dynamic, records the objects, properties, and relations that are salient at each point of the discourse. The distinction among these components is essential to provide an adequate explanation of such discourse phenomena as cue phrases, referring expressions, and interruptions. The theory of attention, intention, and aggregation of utterances is illustrated in the paper with a number of example discourses. Various properties of discourse are described, and explanations for the behavior of cue phrases, referring expressions, and interruptions are explored. This theory provides a framework for describing the processing of utterances in a discourse. Discourse processing requires recognizing how the utterances of the discourse aggregate into segments, recognizing the intentions expressed in the discourse and the relationships among intentions, and track-ing the discourse through the operation of the mechanisms associated with attentional state. This processing description specifies in these recognition tasks the role of information from the discourse and from the participants &#039; knowledge of the domain. 1
A Manifold Regularization Approach to Calibration Reduction for Sensor%2DNetwork Based Tracking.
The ability to accurately detect the location of a mobile node in a sensor network is important for many artificial intelligence (AI) tasks that range from robotics to context-aware computing. Many previous approaches to the location-estimation problem assume the availability of calibrated data. However, to obtain such data requires great effort. In this paper, we present a manifold regularization approach known as LeMan to calibration-effort reduction for tracking a mobile node in a wireless sensor network. We compute a subspace mapping function between the signal space and the physical space by using a small amount of labeled data and a large amount of unlabeled data. This mapping function can be used online to determine the location of mobile nodes in a sensor network based on the signals received. We use Crossbow MICA2 to setup the network and USB camera array to obtain the ground truth. Experimental results show that we can achieve a higher accuracy with much less calibration effort as compared to several previous systems.
Tensor Embedding Methods.

Locally Linear Models on Face Appearance Manifolds with Application to Dual%2DSubspace Based Classification.

Graph Laplacian Kernels for Object Classification from a Single Example.
Classification with only one labeled example per class is a challenging problem in machine learning and pattern recognition. While there have been some attempts to address this problem in the context of specific applications, very little work has been done so far on the problem under more general object classification settings. In this paper, we propose a graph-based approach to the problem. Based on a robust path-based similarity measure proposed recently, we construct a weighted graph using the robust path-based similarities as edge weights. A kernel matrix, called graph Laplacian kernel, is then defined based on the graph Laplacian. With the kernel matrix, in principle any kernel-based classifier can be used for classification. In particular, we demonstrate the use of a kernel nearest neighbor classifier on some synthetic data and real-world image sets, showing that our method can successfully solve some difficult classification tasks with only very few labeled examples. 1.
Extending Kernel Fisher Discriminant Analysis with the Weighted Pairwise Chernoff Criterion.
Abstract. Many linear discriminant analysis (LDA) and kernel Fisher discriminant analysis (KFD) methods are based on the restrictive assumption that the data are homoscedastic. In this paper, we propose a new KFD method called heteroscedastic kernel weighted discriminant analysis (HKWDA) which has several appealing characteristics. First, like all kernel methods, it can handle nonlinearity efficiently in a disciplined manner. Second, by incorporating a weighting function that can capture heteroscedastic data distributions into the discriminant criterion, it can work under more realistic situations and hence can further enhance the classification accuracy in many real-world applications. Moreover, it can effectively deal with the small sample size problem. We have performed some face recognition experiments to compare HKWDA with several linear and nonlinear dimensionality reduction methods, showing that HKWDA consistently gives the best results. 1
Face Recognition with Image Sets Using Hierarchically Extracted Exemplars from Appearance Manifolds.
An unsupervised nonparametric approach is proposed to automatically extract representative face samples (exemplars) from a video sequence or an image set for multipleshot face recognition. Motivated by a nonlinear dimensionality reduction algorithm called Isomap, we use local neighborhood information to approximate the geodesic distances between face images. A hierarchical agglomerative clustering (HAC) algorithm is then applied to group similar faces together based on the estimated geodesic distances which approximate their locations on the appearance manifold. We define the exemplars as cluster centers for template matching at the subsequent testing stage. The final recognition is the outcome of a majority voting scheme which combines the decisions from all the individual frames in the test set. Experimental results on a 40-subject video database demonstrate the effectiveness and flexibility of our proposed method. 
Solution Path for Semi%2DSupervised Classification with Manifold Regularization.

Facial Expression Recognition using Advanced Local Binary Patterns
This paper proposes a novel facial expression recognition approach based on two sets of features extracted from the face images: texture features and global appearance features. The first set is obtained by using the extended local binary patterns in both intensity and gradient maps and computing the Tsallis entropy of the Gabor filtered responses. The second set of features is obtained by performing nullspace based linear discriminant analysis on the training face images. The proposed method is evaluated by extensive experiments on the JAFFE database, and compared with two widely used facial expression recognition approaches. Experimental results show that the proposed approach maintains high recognition rate in a wide range of resolution levels and outperforms the other alternative methods. Index Terms — Face recognition, Machine vision, 1.
Local Discriminant Embedding with Tensor Representation.

Two%2Ddimensional solution path for support vector regression.
Recently, a very appealing approach was proposed to compute the entire solution path for support vector classification (SVC) with very low extra computational cost. This approach was later extended to a support vector regression (SVR) model called ɛ-SVR. However, the method requires that the error parameter ɛ be set a priori, which is only possible if the desired accuracy of the approximation can be specified in advance. In this paper, we show that the solution path for ɛ-SVR is also piecewise linear with respect to ɛ. We further propose an efficient algorithm for exploring the two-dimensional solution space defined by the regularization and error parameters. As opposed to the algorithm for SVC, our proposed algorithm for ɛ-SVR initializes the number of support vectors to zero and then increases it gradually as the algorithm proceeds. As such, a good regression function possessing the sparseness property can be obtained after only a few iterations. 1.
Defending Against TCP SYN Flooding Attacks Under Different Types of IP Spoofing.
TCP-based flooding attacks are a common form of Distributed Denial-of-Service (DDoS) attacks which abuse network resources and can bring about serious threats to the Internet. Incorporating IP spoofing makes it even more difficult to defend against such attacks. Among different IP spoofing techniques, which include random spoofing, subnet spoofing and fixed spoofing, subnet spoofing is the most difficult type to fight against. In this paper, we propose a simple and efficient method to detect and defend against TCP SYN flooding attacks under different IP spoofing types, including subnet spoofing. The method makes use of a storage-efficient data structure and a change-point detection method to distinguish complete three-way TCP handshakes from incomplete ones. Simulation experiments consistently show that our method is both efficient and effective in defending against TCP-based flooding attacks under different IP spoofing types. 1
Intrusion Detection Routers Design

Model%2Dbased transductive learning of the kernel matrix.
This paper addresses the problem of transductive learning of the kernel matrix from a probabilistic per-spective. We define the kernel matrix as a Wishart process prior and construct a hierarchical generative model for kernel matrix learning. Specifically, we consider the target kernel matrix as a random matrix following the Wishart distribution with a positive definite parameter matrix and a degree of freedom. This parameter matrix, in turn, has the inverted Wishart distribution (with a positive definite hyperpa-rameter matrix) as its conjugate prior and the degree of freedom is equal to the dimensionality of the feature space induced by the target kernel. Resorting to a missing data problem, we devise an expectation-maximization (EM) algorithm to infer the missing data, parameter matrix and feature dimensionality in a maximum a posteriori (MAP) manner. Using different settings for the target kernel and hyperparameter matrices, our model can be applied to different types of learning problems. In particular, we consider its application in a semi-supervised learning setting and present two classification methods. Classification experiments are reported on some benchmark data sets with encouraging results. In addition, we also devise the EM algorithm for kernel matrix completion.
Relaxational metric adaptation and its application to semi%2Dsupervised clustering and content%2Dbased image retrieval.
The performance of many supervised and unsupervised learning algorithms is very sensitive to the choice of an appropriate distance metric. Previous work in metric learning and adaptation has mostly been focused on classification tasks by making use of class label information. In standard clustering tasks, however, class label in-formation is not available. In order to adapt the metric to improve the clustering results, some background knowledge or side information is needed. One useful type of side information is in the form of pairwise similarity or dissimilarity information. Recently, some novel methods (e.g., the parametric method proposed by Xing et al.) for learning global metrics based on pairwise side information have been shown to demonstrate promising results. In this paper, we propose a nonparametric method, called relaxational metric adaptation (RMA), for the same metric adaptation prob-lem. While RMA is local in the sense that it allows locally adaptive metrics, it is also global because even patterns not in the vicinity can have long-range effects on the metric adaptation process. Experimental results for semi-supervised clustering based on both simulated and real-world data sets show that RMA outperforms Xing Preprint submitted to Elsevier Science 28 July 2005 et al.’s method under most situations. Besides applying RMA to semi-supervised learning, we have also used it to improve the performance of content-based image retrieval systems through metric adaptation. Experimental results based on two real-world image databases show that RMA significantly outperforms other meth-ods in improving the image retrieval performance.
Extending the relevant component analysis algorithm for metric learning using both positive and negative equivalence constraints.
Relevant component analysis (RCA) is a recently proposed metric learning method for semi-supervised learning applications. It is a simple and efficient method that has been applied successfully to give impressive results. However, RCA can make use of supervisory information in the form of positive equivalence constraints only. In this paper, we propose an extension to RCA that allows both positive and negative equivalence constraints to be incorporated. Experimental results show that the extended RCA algorithm is effective. Key words: metric learning, Mahalanobis metric, semi-supervised learning. 1
Robust locally linear embedding.
In the past few years, some nonlinear dimensionality reduction (NLDR) or nonlinear manifold learning methods have aroused a great deal of interest in the machine learning community. These methods are promising in that they can automatically discover the low-dimensional nonlinear manifold in a high-dimensional data space and then embed the data points into a low-dimensional embedding space, using tractable linear algebraic techniques that are easy to implement and are not prone to local minima. Despite their appealing properties, these NLDR methods are not robust against outliers in the data, yet so far very little has been done to address the robustness problem. In this paper, we address this problem in the context of an NLDR method called locally linear embedding (LLE). Based on robust estimation techniques, we propose an approach to make LLE more robust. We refer to this approach as robust locally linear embedding (RLLE). We also present several specific methods for realizing this general RLLE approach. Experimental results on both synthetic and realworld data show that RLLE is very robust against outliers.
Locally linear metric adaptation with application to semi%2Dsupervised clustering and image retrieval.

Throttling spoofed SYN flooding traffic at the source.

Robust Path%2DBased Spectral Clustering with Application to Image Segmentation.
Spectral clustering and path-based clustering are two recently developed clustering approaches that have delivered impressive results in a number of challenging clustering tasks. However, they are not robust enough against noise and outliers in the data. In this paper, based on M-estimation from robust statistics, we develop a robust path-based spectral clustering method by defining a robust path-based similarity measure for spectral clustering. Our method is significantly more robust than spectral clustering and path-based clustering. We have performed experiments based on both synthetic and real-world data, comparing our method with some other methods. In particular, color images from the Berkeley Segmentation Dataset and Benchmark are used in the image segmentation experiments. Experimental results show that our method consistently outperforms other methods due to its higher robustness.
Nonlinear dimensionality reduction for classification using kernel weighted subspace method.
Abstract--We study the use of kernel subspace methods that learn low-dimensional subspace representations for classification tasks. In particular, we propose a new method called kernel weighted nonlinear discriminant analysis (KWNDA) which possesses several appealing properties. First, like all kernel methods, it handles nonlinearity in a disciplined manner that is also computationally attractive. Second, by introducing weighting functions into the discriminant criterion, it outperforms existing kernel discriminant analysis methods in terms of the classification accuracy. Moreover, it also effectively deals with the small sample size problem. We empirically compare different subspace methods with respect to their classification performance of facial images based on the simple nearest neighbor rule. Experimental results show that KWNDA substantially outperforms competing linear as well as nonlinear subspace methods. 1.
Kernel%2DBased Metric Adaptation with Pairwise Constraints.
Abstract. Many supervised and unsupervised learning algorithms depend on the choice of an appropriate distance metric. While metric learning for supervised learning tasks has a long history, extending it to learning tasks with weaker supervisory information has only been studied very recently. In particular, several methods have been proposed for semi-supervised metric learning based on pairwise (dis)similarity information. In this paper, we propose a kernel-based approach for nonlinear metric learning, which performs locally linear translation in the kernelinduced feature space. We formulate the metric learning problem as a kernel learning problem and solve it efficiently by kernel matrix adaptation. Experimental results based on synthetic and real-world data sets show that our approach is promising for semi-supervised metric learning. 1
Bayesian Inference on Principal Component Analysis Using Reversible Jump Markov Chain Monte Carlo.

Super%2DResolution through Neighbor Embedding.
Abstract. Biometric Person Authentication such as face, fingerprint, palmprint and signature depends on the quality of image processing. When it needs to be done under a low-resolution image, the accuracy will be impaired. So how to recover the lost information from downsampled images is important for both authentication and preprocessing. Based on Super-Resolution through Neighbor Embedding algorithm and histogram matching, we propose an improved super-resolution approach to choose more reasonable training images. First, the training image are selected by histogram matching. Second, neighbor embedding algorithm is employed to recover the high-resolution image. Experiments in several images show that our improved super-resolution approach is promising for potential applications such as low-resolution mobile phone or CCTV (Closed Circuit Television) image person authentication. 1
Reinforcement Learning in Episodic Non%2Dstationary Markovian Environments.

SVC2004 First International Signature Verification Competition.
Abstract. Handwritten signature is the most widely accepted biometric for identity verification. To facilitate objective evaluation and comparison of algorithms in the field of automatic handwritten signature verification, we organized the First International Signature Verification Competition (SVC2004) recently as a step towards establishing common benchmark databases and benchmarking rules. For each of the two tasks of the competition, a signature database involving 100 sets of signature data was created, with 20 genuine signatures and 20 skilled forgeries for each set. Eventually, 13 teams competed for Task 1 and eight teams competed for Task 2. When evaluated on data with skilled forgeries, the best team for Task 1 gives an equal error rate (EER) of 2.84 % and that for Task 2 gives an EER of 2.89%. We believe that SVC2004 has successfully achieved its goals and the experience gained from SVC2004 will be very useful to similar activities in the future. 1
Bayesian inference for transductive learning of kernel matrix using the Tanner%2DWong data augmentation algorithm.
In kernel methods, an interesting recent development  seeks to learn a good kernel from  empirical data automatically. In this paper,  by regarding the transductive learning  of the kernel matrix as a missing data  problem, we propose a Bayesian hierarchical  model for the problem and devise the  Tanner-Wong data augmentation algorithm  for making inference on the model. The  Tanner-Wong algorithm is closely related to  Gibbs sampling, and it also bears a strong resemblance  to the expectation-maximization  (EM) algorithm. For an e#cient implementation,  we propose a simplified Bayesian hierarchical  model and the corresponding TannerWong  algorithm. We express the relationship  between the kernel on the input space  and the kernel on the output space as a  symmetric-definite generalized eigenproblem.
Locally linear metric adaptation for semi%2Dsupervised clustering.
Many supervised and unsupervised learning algorithms are very sensitive to the choice of an appropriate distance metric. While classification tasks can make use of class label information for metric learning, such information is generally unavailable in conventional clustering tasks. Some recent research sought to address a variant of the conventional clustering problem called semi-supervised clustering, which performs clustering in the presence of some background knowledge or supervisory information expressed as pairwise similarity or dissimilarity constraints. However, existing metric learning methods for semisupervised clustering mostly perform global metric learning through a linear transformation. In this paper, we propose a new metric learning method which performs nonlinear transformation globally but linear transformation locally. In particular, we formulate the learning problem as an optimization problem and present two methods for solving it. Through some toy data sets, we show empirically that our locally linear metric adaptation (LLMA) method can handle some difficult cases that cannot be handled satisfactorily by previous methods. We also demonstrate the effectiveness of our method on some real data sets. 1.
IDR An Intrusion Detection Router for Defending against Distributed Denial%2Dof%2DService %28DDoS%29 Attacks.

Surrogate maximization%2Fminimization algorithms for AdaBoost and the logistic regression model.
Surrogate maximization (or minimization)  (SM) algorithms are a family of algorithms  that can be regarded as a generalization of  expectation-maximization (EM) algorithms.
IDR An Intrusion Detection Router for Defending against Distributed Denial%2Dof%2DService %28DDoS%29 Attacks.

Time series clustering with ARMA mixtures.

Parametric Distance Metric Learning with Label Information.
Distance-based methods in pattern recognition and machine learning have to rely on a similarity or dissimilarity measure between patterns in the input space. For many applications, Euclidean distance in the input space is not a good choice and hence more complicated distance metrics have to be used. In this paper, we propose a parametric method for distance metric learning based on class label information. We first define a dissimilarity measure that can be proved to be a metric. It has the favorable property that between-class dissimilarity is always larger than within-class dissimilarity. We then perform parametric learning to find a regression mapping from the input space to an Euclidean feature space, such that the dissimilarity between patterns in the input space is approximated by the Euclidean distance between points in the feature space. Parametric learning is performed using the iterative majorization algorithm. Our method has been tested on some synthetic and real-world benchmark datasets. Experimental results show that this approach is promising.
Host%2Dbased intrusion detection using dynamic and static behavioral models.
Intrusion detection has emerged as an importantapproach to network security. In this paper, we adopt an anomaly detection approach by detecting possible intrusions based on program or user pro les built from normal usage data. In particular, program pro les based on Unix system calls and user pro les based on Unix shell commands are modeled using two di erent types of behavioral models for data mining. The dynamic modeling approach isbased on hidden Markov models (HMM) and the principle of maximum likelihood, while the static modeling approach isbasedonevent occurrence frequency distributions and the principle of minimum cross entropy. The novelty detection approach is adopted to estimate the model parameters using normal training data only, as opposed to the classi cation approach which has to use both normal and intrusion data for training. To determine whether or not a certain behavior is similar enough to the normal model and hence should be classi ed as normal, we use a scheme that can be justi ed from the perspective of hypothesis testing. Our experimental results show that the dynamic modeling approach is better than the static modeling approach for the system call datasets, while the dynamic modeling approach is worse for the shell command datasets. Moreover, the static modeling approach is similar in performance to instance-based learning reported previously by others for the same shell command database but with much higher computational and storage requirements than our method.
Mixtures of ARMA Models for Model%2DBased Time Series Clustering.
Clustering problems are central to many knowledge discovery and data mining tasks. However, most existing clustering methods can only work with fixed-dimensional representations of data patterns. In this paper, we study the clustering of data patterns that are represented as sequences or time series possibly of di#erent lengths. We propose a model-based approach to this problem using mixtures of autoregressive moving average (ARMA) models. We derive an expectation-maximization (EM) algorithm for learning the mixing coe#cients as well as the parameters of the component models. The algorithm can determine the number of clusters in the data automatically. Experiments were conducted on a number of simulated and real datasets. Results from the experiments show that our method compares favorably with another method recently proposed by others for similar time series clustering problems.
Parzen%2DWindow Network Intrusion Detectors.
Network intrusion detection is the problem of detecting anomalous network connections caused by intrusive activities. Many intrusion detection systems proposed before use both normal and intrusion data to build their classifiers. However, intrusion data are usually scarce and difficult to collect. We propose to solve this problem using a novelty detection approach. In particular, we propose to take a nonparametric density estimation approach based on Parzen-window estimators with Gaussian kernels to build an intrusion detection system using normal data only. To facilitate comparison, we have tested our system on the KDD Cup 1999 dataset. Our system compares favorably with the KDD Cup winner which is based on an ensemble of decision trees with bagged boosting, as our system uses no intrusion data at all and much less normal data for training.
User Profiling for Intrusion Detection Using Dynamic and Static Behavioral Models.

Bidirectional Deformable Matching with Application to Handwritten Character Extraction.
To achieve integrated segmentation and recognition in complex scenes, the model-based approach has widely been accepted as a promising paradigm. However, the performance is still far from satisfactory when the target object is highly deformed and the level of outlier contamination is high. In this paper, we first describe two Bayesian frameworks, one for classifying input patterns and another for detecting target patterns in complex scenes using deformable models. Then, we show that the two frameworks are similar to the forward-reverse setting of Hausdorff matching and that their matching and discriminating properties are complementary to each other. By properly combining the two frameworks, we propose a new matching scheme called bidirectional matching. This combined approach inherits the advantages of the two Bayesian frameworks. In particular, we have obtained encouraging empirical results on shape-based pattern extraction, using a subset of the CEDAR handwriting database containing handwritten words of highly varying shape. Index Terms: Model-based segmentation, deformable models, Bayesian inference, bidirectional matching, Hausdorff matching.  An abridged version of this paper was published in [1].  Dr. Kwok-Wai Cheung is the correspondence author. 1 1
On deformable models for visual pattern recognition.
This paper reviews model-based methods  fornon-rig#  shape  recogLj#If8  These methods model, match  andclassif non-rigg  shapes, which  aregefIxq#x  problematic for  conventationalalgentati using rigg  models.
PenCalc A Novel Application of On%2DLine Mathematical Expression Recognition Technology.
Most of the calculator programs found in existing penbased mobile computing devices, such as personal digital assistants (PDA) and other handheld devices, do not take full advantages of the pen technology offered by these devices. Instead, input of expressions is still done through a virtual keypad shown on the screen, and the stylus (i.e., electronic pen) is simply used as a pointing device. In this paper, we propose an intelligent handwriting-based calculator program with which the user can enter expressions simply by writing them on the screen using a stylus. In addition, variables can be defined to store intermediate results for subsequent calculations, as in ordinary algebraic calculations. The proposed software is the result of a novel application of on-line mathematical expression recognition technology which has mostly been used by others only for some mathematical expression editor programs.  1. 
Hidden%2DMode Markov Decision Processes for Nonstationary Sequential Decision Making.
This paper mainly addresses the first and third conditions, whereas the second condition is only briefly discussed. In particular, we are interested in a special type of nonstationary environments that repeat their dynamics in a certain manner. We propose a formal model for such environments. We also develop algorithms for learning the model parameters and for computing optimal policies. Before we proceed, let us briefly review the four categories of problems shown in Figure 1 and define the terminology that will be used in this paper
Error detection
Error concealment techniques are useful in video transmission over channels that introduce bit errors. The efficiency and result of error concealment technique, however, rely on the error detection capabilities of video decoders. A novel error detection technique employing fragile watermarking is proposed in this paper. By embedding a fragile watermark on the quantized DCT coefficients and examining its integrity on the decoder side, the error detection capability of video decoders is significantly increased compared to widely used syntax-based error detection schemes.
Mathematical expression recognition a survey.
. Automatic recognition of mathematical expressions is one of the key vehicles in the drive towards transcribing documents in scientific and engineering disciplines into electronic form. This problem typically consists of two major stages, namely, symbol recognition and structural analysis. In this survey paper, we will review most of the existing work with respect to each of the two major stages of the recognition process. In particular, we try to put emphasis on the similarities and differences between systems. Moreover, some important issues in mathematical expression recognition will be addressed in depth. All these together serve to provide a clear overall picture of how this research area has been developed to date.  Key words: error detection and correction -- mathematical expression recognition -- performance evaluation -- structural analysis -- symbol recognition  1 
An efficient syntactic approach to structural analysis of on%2Dline handwritten mathematical expressions.
Machine recognition of mathematical expressions is not trivial even when all the individual characters and symbols in an expression can be recognized correctly. In this paper, we propose to use definite clause grammar (DCG) as a formalism to de&#034;ne a set of replacement rules for parsing mathematical expressions. With DCG, we are not only able to define the replacement rules concisely, but their definitions are also in a readily executable form. However, a DCG parser is potentially inefficient due to its frequent use of backtracking. Thus, we propose some methods here to increase the efficiency of the parsing process. Experiments done on some commonly seen mathematical expressions show that our proposed methods can achieve quite satisfactory speedup, making mathematical expression recognition more feasible for real-world applications.  
A Bidirectional Matching Algorithm for Deformable Pattern Detection with Application to Handwritten Word Retrieval.
A Bayesian framework for deformable pattern classification has been proposed in [1] with promising results for isolated handwritten character recognition. Its performance, however, degrades significantly when it is applied to detect deformable patterns in complex scenes, where the amount of outliers due to other neighboring objects or the background is usually large. Also, the fact that the associated evidence measure does not penalize models resting on white space results in a high false alarm rate. In this paper, another Bayesian framework for deformable pattern detection is proposed. The framework possesses the intrinsic property of matching with only part of an image (segmentation) and its associated evidence measure can penalize white space implicitly. However, limited data exploration capability is the major trade-off. By properly combining the two frameworks, a new matching algorithm called bidirectional matching is proposed. This combined approach possesses the advantages of th...
An Environment Model for Nonstationary Reinforcement Learning.
Reinforcement learning in nonstationary environments is generally  regarded as an important and yet difficult problem. This paper  partially addresses the problem by formalizing a subclass of nonstationary  environments. The environment model, called hidden-mode  Markov decision process (HM-MDP), assumes that environmental  changes are always confined to a small number of hidden modes.  A mode basically indexes a Markov decision process (MDP) and  evolves with time according to a Markov chain. While HM-MDP  is a special case of partially observable Markov decision processes  (POMDP), modeling an HM-MDP environment via the more general  POMDP model unnecessarily increases the problem complexity.  A variant of the Baum-Welch algorithm is developed for model  learning requiring less data and time.  1 Introduction  Reinforcement Learning (RL) [7] is a learning paradigm based upon the framework of Markov decision process (MDP). Traditional RL research assumes that environment dynamics (i.e....
Recognizing on%2Dline handwritten alphanumeric characters through flexible structural matching.
Speed, accuracy, and flexibility are crucial to the practical use of on-line handwriting recognition. Besides, extensibility is also an important concern as we move from one domain to another which requires the character set to be extended. In this paper, we will propose a simple yet robust structural approach for recognizing on-line handwriting. Our approach is designed to achieve reasonable speed, fairly high accuracy and sufficient tolerance to variations. At the same time, it maintains a high degree of reusability and hence facilitates extensibility. Experimental results show that the recognition rates are 98.60% for digits, 98.49% for uppercase letters, 97.44% for lowercase letters, and 97.40% for the combined set. When the rejected cases are excluded from the calculation, the rates can be increased to 99.93%, 99.53%, 98.55% and 98.07%, respectively. On the average, the recognition speed is about 7.5 characters per second running in Prolog on a Sun SPARC 10 Unix workstation and the m...
Towards Efficient Structural Analysis of Mathematical Expressions.
Machine recognition of mathematical expressions is not trivial even when all the individual characters and symbols in an expression can be recognized correctly. In this paper, we propose to use Definite Clause Grammar (DCG) as a formalism to define a set of replacement rules for parsing mathematical expressions. With DCG, we are not only able to define the replacement rules concisely, but their definitions are also in a readily executable form. However, backtracking parsers like Prolog interpreters, which execute DCG directly, are by nature inefficient. Thus we propose some methods here to increase the efficiency of the parsing process. Experiments done on some typical mathematical expressions show that our proposed methods can achieve speedup ranging from 10 to 70 times, making mathematical expression recognition more feasible for real-world applications.
A Bayesian Framework for Deformable Pattern Recognition With Application to Handwritten Character Recognition.
Deformable models have recently been proposed for many pattern recognition applications due to their ability to handle large shape variations. These proposed approaches represent patterns or shapes as deformable models, which deform themselves to match with the input image, and subsequently feed the extracted information into a classifier. The three components---modeling, matching, and classification---are  often treated as independent tasks. In this paper, we study how to integrate deformable models into a Bayesian framework as a unified approach for modeling, matching, and classifying shapes. Handwritten character recognition serves as a testbed for evaluating the approach. With the use of our system, recognition is invariant to affine transformation as well as other handwriting variations. In addition, no preprocessing or manual setting of hyperparameters (e.g., regularization parameter and character width) is required. Besides, issues on the incorporation of constraints on model fl...
On%2Dline handwritten alphanumeric character recognition using dominant points in strokes.

Competitive Mixture of Deformable Models for Pattern Classification.
Following the success of applying deformable models to feature extraction, a natural next step is to apply such models to pattern classification. Recently, we have cast a deformable model under a Bayesian framework for classification, giving promising results. However, deformable model methods are computationally expensive due to the required iterative optimization process. The problem is even more severe when there are a large number of models (e.g., for character recognition), because each of them has to deform and match with the input data before a final classification can be derived. In this paper, we propose to combine the deformable models into a mixture, in which the individual models compete with each other to survive the matching process during classification. Models that do not compete well are eliminated early, thus allowing substantial savings in computation. This process of competition-elimination has been applied to handwritten digit recognition in which significant speedup can be achieved without sacrificing recognition accuracy.
Bayesian Regularization in Constructive Neural Networks.
. In this paper, we study the incorporation of Bayesian regularization into constructive neural networks. The degree of regularization is automatically controlled in the Bayesian inference framework and hence does not require manual setting. Simulation shows that regularization, with input training using a full Bayesian approach, produces networks with better generalization performance and lower susceptibility to over-fitting as the network size increases. Regularization with input training under MacKay&#039;s evidence framework, however, does not produce significant improvement on the problems tested. 1 Introduction  Multi-layer feedforward networks have been popularly used in many pattern classification and regression problems. While standard back-propagation performs gradient descent in the weight space of a network with fixed topology, constructive  procedures [4] start with a small network and then grow additional hidden units and weights until a satisfactory solution is found. A parti...
A grammatical inference approach to on%2Dline handwriting modeling and recognition a pilot study.

On%2DLine Handwritten Alphanumeric Character Recognition Using Feature Sequences.

Predictive Q%2DRouting A Memory%2Dbased Reinforcement Learning Approach to Adaptive Traffic Control.
In this paper, we propose a memory-based Q-learning algorithm called predictive Q-routing (PQ-routing) for adaptive traffic control. We attempt to address two problems encountered in Q-routing (Boyan &amp; Littman, 1994), namely, the inability to fine-tune routing policies under low network load and the inability to learn new optimal policies under decreasing load conditions. Unlike other memory-based reinforcement learning algorithms in which memory is used to keep past experiences to increase learning speed, PQ-routing keeps the best experiences learned and reuses them by predicting the traffic trend. The effectiveness of PQ-routing has been verified under various network topologies and traffic conditions. Simulation results show that PQ-routing is superior to Q-routing in terms of both learning speed and adaptability. 1 INTRODUCTION  The adaptive traffic control problem is to devise routing policies for controllers (i.e. routers) operating in a non-stationary environment to minimize the...
Constructive neural networks as estimators of bayesian discriminant functions.
Of crucial importance to the successful use of artificial neural networks for pattern classification problems is how the appropriate network size can be automatically determined. We address this issue by formulating the process as an automatic search in the space of functions that corresponds to a subclass of multilayer feedforward networks. Learning is thus a dynamic network construction process which involves adjusting both the network weights and the topology. Adding new hidden units corresponds to extracting higher-level features from the original input features for reducing the residual classification errors. It can be shown that the resultant network approximates a Bayesian classifier that implements the Bayesian decision rule for classification. This paper also reports the empirical results of several pattern classification experiments. Keywords: pattern classification, discriminant functions, Bayesian classifiers, feedforward networks, constructive networks, transfer of learni...
A Neural Network Approach to Constructive Induction.
be, 1969] Watanabe, S. (1969). Knowing and Guessing - A Formal and Qualitative  Study. Wiley, New York, NY.  [Weiss and Indurkhya, 1994] Weiss, S. M. and Indurkhya, N. (1994). Small sample decision tree pruning. In 11th International Machine Learning Conference, New Brunswick, NJ.  [Wilson, 1987] Wilson, S. (1987). Classifier systems and the animat problem. Machine Learning, 2:199--228.  [Wittgenstein, 1953] Wittgenstein, L. (1953). In Ascombe, G. E. M., editor, Philosophical  Investigations. Oxford: Blackwell, London, UK.  [Wnek and Michalski, 1994] Wnek, J. and Michalski, R. (1994). Hypothesis-driven constructive induction in aq17-hci: A method and experiments. Machine Learning, 14:136--247.  BIBLIOGRAPHY 159 of the 8th International Workshop on Machine Learning, pages 203--207, Evanston, IL. Morgan Kaufmann.  [Slotta and Chi, 1996] Slotta, J. and Chi, M. T. H. (1996). Understandin
